<HTML>

<HEAD>
<TITLE>ABSTRACT ALGEBRA ON LINE: Integers </TITLE>
</HEAD>

<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">

<BODY>
<H2 align="center"> INTEGERS </H2>
Excerpted from Beachy/Blair,
<B><EM>Abstract Algebra</EM></B>, <EM>2nd Ed.</EM>, <B>&copy;</B> 1996
<H4>Chapter 1</H4>
<dl>
<dd>1.1, 1.2 <A HREF=#divisors>Divisors; prime factorization</A>
<dd>1.3, 1.4 <A HREF=#congruences>Congruences</A>
</dl>
<P>
<a HREF="functions.html">Forward</a>
 |
<a HREF="contents.html#index">Table of Contents</a>
 |
<A HREF="node1.html"> About this document </A>
<P> <HR> <P>

<A NAME=divisors></A>
<H2 align="center"> Divisors; prime factorization </H2>

<A NAME=1100></A>
The set {..., -2, -1, 0, 1, 2, 3, ...} is called the set of
<B>integers</B>, and will be denoted by <B>Z</B>.
<p>

<A NAME=1101></A>
<B>1.1.1. Definition.</B>
An integer a is called a
<A NAME=1101a><B>multiple</B></A>
of an integer b if a=bq for some integer q.
In this case we also say that b is a
<A NAME=1101b><B>divisor</B></A>
of a, and we use the notation b | a.
<p>

In the above case we can also say that b is a
<A NAME=1101c><B>factor</B></A>
of a, or that a is
<B>divisible</B>
by b.  If b is not a divisor of a, meaning that
a <IMG ALT="" SRC="sym/neq.gif"> bq  for all 
q <IMG ALT="" SRC="sym/in.gif"> <B>Z</B>, 
then we write b <IMG ALT="" SRC="sym/nodiv.gif"> a.
The set of all multiples of an integer a will be denoted by
<P ALIGN="center">
a<B>Z</B> = { 
m <IMG ALT="" SRC="sym/in.gif"> <B>Z</B> | m=aq &nbsp; for 
some &nbsp; q <IMG ALT="" SRC="sym/in.gif"> <B>Z</B> }.
</P>
<p>

<A NAME=1102></A>
<B>1.1.2. Axiom. [Well-Ordering Principle]</B>
Every nonempty set of natural numbers contains a smallest element.
<p>

<A NAME=1103></A>
<B>1.1.3 Theorem. [Division Algorithm]</B>
For any integers a and b, with b&gt;0,
there exist unique integers q (the
<B>quotient</B>)
and r (the
<B>remainder</B>)
such that a=bq+r, with 0 <IMG ALT="" SRC="sym/leq.gif"> r&lt;b.
<p>

<A NAME=1104></A>
<B>1.1.4. Theorem.</B>
Let I be a nonempty set of integers
that is closed under addition and subtraction.
Then I either consists of zero alone or else contains
a smallest positive element,
in which case I consists of all multiples
of its smallest positive element.
<p>

<A NAME=1105></A>
<B>1.1.5. Definition.</B>
A positive integer d is called the
<B>greatest common divisor</B>
of the nonzero integers a and b if
<DL>
<DD><B>(i)</B>
d is a divisor of both a and b, &nbsp; and
<P>
<DD><B>(ii)</B>
any divisor of both a and b is also a divisor of d.
</DL>

We will use the notation gcd(a,b), or simply (a,b),
for the greatest common divisor of  a and  b.
<p>

<A NAME=1106></A>
<B>1.1.6. Theorem.</B>
Any two nonzero integers a and b have a greatest common divisor,
which can be expressed as the smallest positive linear combination of a and b.
<BR>
Moreover, an integer is a linear combination of a and b
if and only if it is a multiple of their greatest common divisor.
<p>

The greatest common divisor of two numbers
can be computed by using a procedure known as the
<A NAME=Euclid><B>Euclidean algorithm</B></A>.
First, note that if  a <IMG ALT="" SRC="sym/neq.gif"> 0 and  
b | a, then gcd(a,b) = |b|.
The next observation provides the basis for the Euclidean algorithm.
If a=bq+r, then (a,b)=(b,r).
Thus given integers a&gt;b&gt;0, 
the Euclidean algorithm uses the division algorithm repeatedly to obtain
<P ALIGN="center">
a = bq<sub>1</sub> + r<sub>1</sub>, &nbsp; with 
0 <IMG ALT="" SRC="sym/leq.gif"> r<sub>1</sub>&lt; b 
<BR>
b = r<sub>1</sub>q<sub>2</sub> + r<sub>2</sub>, &nbsp; with 
0 <IMG ALT="" SRC="sym/leq.gif"> r<sub>2</sub>&lt; r<sub>1</sub>,
<BR>
etc.
</P>
Since r<sub>1</sub> &gt; r<sub>2</sub> &gt; . . . , 
the remainders get smaller and smaller,
and after a finite number of steps we obtain a remainder  
r<sub>n+1</sub> = 0.
Thus
gcd(a,b) = gcd(b,r<sub>1</sub>) = . . . = r<sub>n</sub>.
<p>

<A NAME=1201></A>
<B>1.2.1. Definition.</B>
The nonzero integers a and b are said to be
<B>relatively prime</B>
if (a,b)=1.
<p>

<A NAME=1202></A>
<B>1.2.2 Proposition.</B>
Let a,b be nonzero integers.
Then (a,b)=1 if and only if there exist integers m,n such that 
<P align="center">
ma + nb = 1 .
</p>

<B>1.2.3 Proposition.</B>
Let a,b,c be integers.
<DL>
<DD><B>(a)</B>
If b | ac, then b | (a,b)c.
<P>
<DD><B>(b)</B>
If b | ac and (a,b)=1, then b | c.
<P>
<DD><B>(c)</B>
If b | a, c | a and (b,c)=1, then bc | a.
<P>
<DD><B>(d)</B>
(a,bc)=1 if and only if (a,b)=1 and (a,c)=1.
</DL>

<A NAME=1204></A>
<B>1.2.4. Definition.</B>
An integer p&gt;1 is called a
<B>prime number</B>
if its only divisors are &plusmn; 1 and &plusmn; p.
An integer a &gt; 1 is called
<A NAME=1204a><B>composite</B></A>
if it is not prime.
<p>

<A NAME=1205></A>
<B>1.2.5. Lemma. [Euclid]</B>
An integer p&gt;1 is prime if and only if it satisfies the following property:  
If p | ab for integers a and b, then either p | a or p | b.
<p>

<A NAME=1206></A>
<B>1.2.6. Theorem. [Fundamental Theorem of Arithmetic]</B>
Any integer a&gt;1 can be factored uniquely 
as a product of prime numbers, in the form
<P ALIGN="center">
a = 
p<sub>1</sub><sup>m<sub>1</sub></sup>
p<sub>2</sub><sup>m<sub>2</sub></sup>
<B> &middot;  &middot;  &middot;</B>
p<sub>n</sub><sup>m<sub>n</sub></sup>
</P>
where p<sub>1</sub> &lt; p<sub>2</sub> &lt; 
&middot; &middot; &middot; &lt; p<sub>n</sub>
and the exponents
m<sub>1</sub>,
m<sub>2</sub>
, . . . ,
m<sub>n</sub>
are all positive.
<p>

<A NAME=1207></A>
<B>1.2.7. Theorem. [Euclid]</B>
There exist infinitely many prime numbers.
<p>

<A NAME=1208></A>
<B>1.2.8. Definition.</B>
A positive integer m is called the
<B>least common multiple</B>
of the nonzero integers a and b if
<DL>
<DD><B>(i)</B>
m is a multiple of both a and b, &nbsp; and
<P>
<DD><B>(ii)</B>
any multiple of both a and b is also
a multiple of m.
</DL>
We will use the notation lcm[a,b] for the least common multiple of a and b.
<p>

<A NAME=1209></A>
<B>1.2.9. Proposition.</B>
Let a and b be positive integers with prime factorizations
<P align="center">
a =
p<sub>1</sub><sup>a<sub>1</sub></sup>
p<sub>2</sub><sup>a<sub>2</sub></sup>
<B> &middot;  &middot;  &middot; </B>
p<sub>n</sub><sup>a<sub>n</sub></sup>
&nbsp; &nbsp; and &nbsp; &nbsp; b =
p<sub>1</sub><sup>b<sub>1</sub></sup>
p<sub>2</sub><sup>b<sub>2</sub></sup>
<B> &middot;  &middot;  &middot; </B>
p<sub>n</sub><sup>b<sub>n</sub></sup> ,
</P>
where
a<sub>i</sub>  <IMG ALT="" SRC="sym/geq.gif"> 0 and 
b<sub>i</sub>  <IMG ALT="" SRC="sym/geq.gif"> 0 
for all i (allowing use of the same prime factors.)
<BR>
For each i let 
d<sub>i</sub>
=min { a<sub>i</sub>, b<sub>i</sub> } 
and let 
m<sub>i</sub>
=max { a<sub>i</sub>, b<sub>i</sub> }.
Then we have the following factorizations:
<DL>
<DD><B>(a)</B>
gcd(a,b) =
p<sub>1</sub><sup>d<sub>1</sub></sup>
p<sub>2</sub><sup>d<sub>2</sub></sup>
<B> &middot;  &middot;  &middot; </B>
p<sub>n</sub><sup>d<sub>n</sub></sup>
<P>
<DD><B>(b)</B>
lcm[a,b] =
p<sub>1</sub><sup>m<sub>1</sub></sup>
p<sub>2</sub><sup>m<sub>2</sub></sup>
<B> &middot;  &middot;  &middot; </B>
p<sub>n</sub><sup>m<sub>n</sub></sup>
</DL>

<A NAME=congruences></A>
<H2 align="center"> Congruences </H2>

<A NAME=1301></A>
<B>1.3.1. Definition.</B>
Let n be a positive integer.
Integers a and b are said to be
<B>congruent modulo n</B>
if they have the same remainder when divided by n.
This is denoted by writing
a  <IMG ALT="" SRC="sym/equiv.gif">  b (mod n).
<p>

<B>1.3.2. Proposition.</B>
Let a,b, and n&gt;0 be integers.  Then 
a  <IMG ALT="" SRC="sym/equiv.gif">  b (mod n) 
if and only if n | (a-b).
<p>

When working with congruence modulo n, the integer n is called the
<A NAME=modulus><B>modulus</B>.</A>
By the preceding proposition,
a  <IMG ALT="" SRC="sym/equiv.gif">  b (mod n)
if and only if a-b=nq for some integer q.
We can write this in the form a=b+nq, for some integer q.
This observation gives a very useful method of replacing
a congruence with an equation (over <B>Z</B>).
On the other hand, Proposition 1.3.3 shows that
any equation can be converted to a congruence modulo n
by simply changing the = sign to  <IMG ALT="" SRC="sym/equiv.gif"> .  
In doing so, any term congruent to 0 can simply be omitted.
Thus the equation a=b+nq would be converted back to
a  <IMG ALT="" SRC="sym/equiv.gif">  b (mod n).
<p>

<B>1.3.3 Proposition.</B>
Let n&gt;0 be an integer.
Then the following conditions hold for all integers a,b,c,d:
<DL>
<DD><B>(a)</B>
If a  <IMG ALT="" SRC="sym/equiv.gif">  c (mod n) and 
b  <IMG ALT="" SRC="sym/equiv.gif">  d (mod n), then
<P align="center">
then a <IMG ALT="" SRC="sym/pm.gif"> b
 <IMG ALT="" SRC="sym/equiv.gif"> 
c <IMG ALT="" SRC="sym/pm.gif"> d (mod n),
and ab  <IMG ALT="" SRC="sym/equiv.gif">  cd (mod n).
</P>
<DD><B>(b)</B>
If a+c  <IMG ALT="" SRC="sym/equiv.gif">  a+d (mod n), then 
c  <IMG ALT="" SRC="sym/equiv.gif">  d (mod n).
<P>
If ac  <IMG ALT="" SRC="sym/equiv.gif">  ad (mod n) and (a,n)=1, 
then c  <IMG ALT="" SRC="sym/equiv.gif">  d (mod n).
</DL>

<B>1.3.4. Proposition.</B>
Let a and n&gt;1 be integers.
There exists an integer b such that 
ab  <IMG ALT="" SRC="sym/equiv.gif">  1 (mod n) if and only if (a,n)=1.
<p>

<B>1.3.5. Theorem.</B>
The congruence ax  <IMG ALT="" SRC="sym/equiv.gif">  b (mod n) 
has a solution if and only if b is divisible by d, where d=(a,n).
<BR>
If d | b, then there are d distinct solutions modulo n,
and these solutions are congruent modulo n / d.
<p>

<A NAME=1306></A>
<B>1.3.6. Theorem. [Chinese Remainder Theorem]</B>
Let n and m be positive integers, with (n,m)=1.
Then the system of congruences
<P ALIGN="center">
x  <IMG ALT="" SRC="sym/equiv.gif">  a (mod n)
&nbsp; &nbsp; &nbsp;
x  <IMG ALT="" SRC="sym/equiv.gif">  b (mod m)
</P>
has a solution.
Moreover, any two solutions are congruent modulo mn.
<p>

<A NAME=1401></A>
<B>1.4.1. Definition.</B>
Let a and n&gt;0 be integers.
The set of all integers which have the same remainder as a 
when divided by n is called the
<B>congruence class</B>
of a modulo n, and is denoted by 
[a]<sub>n</sub>, where
<P ALIGN="center">
[a]<sub>n</sub> =
{ x  <IMG ALT="" SRC="sym/in.gif">  <B>Z</B> |  
x  <IMG ALT="" SRC="sym/equiv.gif">  a (mod n) }.
</P>
The collection of all congruence classes modulo n is called the
<A NAME=1401a><B>set of integers modulo n</B>,</A>
denoted by <B>Z</B><sub>n</sub>.
<p>

<B>1.4.2 Proposition.</B>
Let n be a positive integer, and let a,b be any integers.
Then the addition and multiplication of congruence classes
given below are well-defined:
<P ALIGN="center">
[a]<sub>n</sub> + [b]<sub>n</sub> = [a+b]<sub>n</sub> ,
&nbsp; &nbsp; &nbsp;
[a]<sub>n</sub>[b]<sub>n</sub> = [ab]<sub>n</sub>.
</P>

<A NAME=1403></A>
<B> 1.4.3. Definition. </B>
If [a]<sub>n</sub>
belongs to <B>Z</B><sub>n</sub>,
and [a]<sub>n</sub>[b]<sub>n</sub> = [0]<sub>n</sub>
for some nonzero congruence class [b]<sub>n</sub>, then 
[a]<sub>n</sub> is called a
<B>divisor of zero</B>,
modulo n.
<p>

<B>1.4.4. Definition.</B>
If [a]<sub>n</sub> belongs to 
<B>Z</B><sub>n</sub>, and 
[a]<sub>n</sub>[b]<sub>n</sub> = [1]<sub>n</sub>, 
for some congruence class [b]<sub>n</sub>, then 
[b]<sub>n</sub> is called a
<B> multiplicative inverse </B>
of [a]<sub>n</sub> and is denoted by 
[a]<sub>n</sub><sup>-1</sup>.
<BR>
In this case, we say that 
[a]<sub>n</sub> and [b]<sub>n</sub> are
<B>invertible</B>
elements of 
<B>Z</B><sub>n</sub>, or
<B>units</B>
of <B>Z</B><sub>n</sub>.
<p>

<B>1.4.5. Proposition.</B>
Let n be a positive integer.
<DL>
<DD><B>(a)</B>
The congruence class [a]<sub>n</sub>
has a multiplicative inverse
in <B>Z</B><sub>n</sub>
if and only if (a,n)=1.
<P>
<DD><B>(b)</B>
A nonzero element of 
<B>Z</B><sub>n</sub>
either has a multiplicative inverse or is a divisor of zero.
</DL>

<B>1.4.6. Corollary.</B>
The following conditions on the modulus n &gt; 0 are equivalent:
<DL>
<DD><B>(1)</B>
The number n is prime.
<P>
<DD><B>(2)</B>
<B>Z</B><sub>n</sub>
has no divisors of zero, except 
[0]<sub>n</sub>.
<P>
<DD><B>(3)</B>
Every nonzero element of 
<B>Z</B><sub>n</sub>
has a multiplicative inverse.
</DL>

<A NAME=1407></A>
<B>1.4.7. Definition.</B>
Let n be a positive integer.
The number of positive integers less than or equal to n which
are relatively prime to n will be denoted by
 <IMG ALT="" SRC="sym/varphi.gif"> (n).  
This function is called
<B>Euler's phi-function</B>,
or the
<B>totient function</B>.
<p>

<A NAME=1408></A>
<B>1.4.8. Proposition.</B>
If the prime factorization of n is
n = 
p<sub>1</sub><sup>m<sub>1</sub></sup>
p<sub>2</sub><sup>m<sub>2</sub></sup>
<B> &middot; &middot; &middot; </B>
p<sub>n</sub><sup>m<sub>n</sub></sup>  ,
then
<P ALIGN="center">
 <IMG ALT="" SRC="sym/varphi.gif"> (n)
= n(1-1/p<sub>1</sub>)(1-1/p<sub>2</sub>)
<B> &middot; &middot; &middot; </B>
(1-1/p<sub>k</sub>).
</P>
<p>

<A NAME=1409></A>
<B>1.4.9. Definition.</B>
The set of units of 
<B>Z</B><sub>n</sub>, 
the congruence classes 
[a]<sub>n</sub>, 
such that (a,n)=1, will be denoted by
<BR>
<B>Z</B><sub>n</sub><sup>&times;</sup>.
<p>

The following theorem shows that raising any congruence class in
<B>Z</B><sub>n</sub><sup>&times;</sup>
to the power  <IMG  ALT="" SRC="sym/varphi.gif"> (n)
yields the congruence class of 1.
It is possible to give a purely number theoretic proof at this point, but in 
<A HREF="groups.html#3212e">Example 3.2.12</A>
there is a more elegant proof using elementary group theory.
<p>

<A NAME=1411></A>
<B> 1.4.11. Theorem. [Euler] </B>
If (a,n)=1, then a<sup>  
<IMG ALT="" SRC="sym/varphi.gif"> (n)</sup>
<IMG ALT="" SRC="sym/equiv.gif"> 1 (mod n).
<p>

<A NAME=1412></A>
<B>1.4.12 Corollary. [Fermat]</B>
If p is prime, then 
a<sup>p</sup>  <IMG ALT="" SRC="sym/equiv.gif"> a (mod p),
for any integer a.

<p> <HR> <p>
<a HREF="functions.html">Forward</a>
 |
<a HREF="contents.html#index">Table of Contents</a>
 |
<A HREF="node1.html"> About this document </A>

<!-- last modified 3/15/2004 -->
</BODY>
</HTML>
